/**
 * Copyright (C) 2008+ Spark Zheng
 *
 * @file	include/misc.h
 * @brief       miscellaneous functions
 * 
 * @module      dlib
 * @see		dlib
 * @history     
 *		version 0.1.0 spark add max/min str_similiar
 */

#ifndef _DLIB_MISC_H
#define _DLIB_MISC_H

#ifdef __cplusplus
extern "C" {
#endif

#include "global.h"

/** 
 * swap_int
 * swap two int objects.
 * @param one: first object(restrict for c99)
 * @param two: second object
 */
static inline void swap_int(int *one, int *two)
{
	if (one == NULL || two == NULL) return;
	*one = *one ^ *two;
	*two = *one ^ *two;
	*one = *one ^ *two;
	return;
}

/** 
 * swap
 * swap two objects.
 * @param one: first object(restrict for c99)
 * @param two: second object
 * @param size: sizeof object
 */
static inline void swap(void *one, void *two, uint32_t size)
{
	if (one == NULL || two == NULL || size == 0) return;
	uint8_t temp[size];
	memmove(temp, one, size);
	memmove(one, two, size);
	memmove(two, temp, size);
	return;
}

/** 
 * quake_sqrt
 * a tale of sqrt, from QUAKE3 by Gary Tarolli.
 * @param x: 
 */
static inline float quake_sqrt(float x)
{   
	float xhalf = 0.5f * x;
	int32_t i = *(int32_t *)&x;
	//i = 0x5f3759df - (i >> 1);
	i = 0x5f37642f - (i >> 1);
	//i = 0x5f375a86 - (i >> 1);
	x = *(float *)&i;
	x = x * (1.5f - xhalf * x * x);
	//x = x * (1.5f - xhalf * x * x);
	return 1.0f / x;
}   

/** 
 * is_primer
 * find a number whether is a primer.
 * @return 1(is a primer) / 0(not a primer)
 * @param n: number
 */
static inline int is_primer(uint32_t n)
{
	uint32_t i;
	for (i = 2; i < quake_sqrt((float)n) + 1; i++) {
		if (n % i == 0) 
			return 0;
	}
	return 1;
}

/** 
 * near_primer
 * find a primer new given number.
 * @param ceil: mostly is floor, but not guaranteed
 */
static inline uint32_t near_primer(uint32_t n)
{
	uint32_t i;
	uint32_t primer = 0;
	uint32_t j = (n + 1) / 6;

	for (i = j; i > 0; i--) {
		primer = 6 * i + 1;
		if (is_primer(primer)) {
			return primer;
		}
		primer = 6 * i - 1;
		if (is_primer(primer)) {
			return primer;
		}
	}
	return 2;
}


/** miscellaneous common functions */
/**
 * max_n
 * calculate the max value of many integers.
 * @deprecated use nmax in global.h
 * @param array: integer array
 * @param n: integers number, [out:] the i' element return
 */
extern int max_n(int *array, int *n);

/** 
 * min_n
 * calculate the min value of many integers.
 * @deprecated use nmin in global.h
 * @param array: integer array
 * @param n: integers number, [out:] the i' element return
 */
extern int min_n(int *array, int *n);

/** 
 * gcd
 * calculate the GCD of two integers.
 * @param one: first integer
 * @param two: second integer
 */
extern uint32_t gcd(uint32_t one, uint32_t two);

/** 
 * gcd_n
 * calculate the GCD of many integers.
 * @param array: integer array
 * @param len: integers number
 */
extern uint32_t gcd_n(uint32_t *array, uint32_t len);

/** 
 * lcm
 * calculate the LCM of two integers.
 * @param one: first integer
 * @param two: second integer
 */
extern uint32_t lcm(uint32_t one, uint32_t two);

/** 
 * lcm_n
 * calculate the LCM of many integers.
 * @param array: integer array
 * @param len: integers number
 */
extern uint32_t lcm_n(uint32_t *array, uint32_t len);

/** miscellaneous schedule functions */
/** 
 * rr_scheduler
 * switch a object round-robin.
 * @param weight: objects weight array, could be NULL
 * @param len: objects number (N)
 * @param prev: previous scheduled object-id (0 - (N-1))
 * @param cw, status words
 */
extern uint32_t rr_scheduler(uint32_t *weight, uint32_t len, uint32_t prev,
			     int *cw);

/**
 * ssm_dp, Sub-Sequence-Match:
 * all diff sub-sequences of A exactly match B
 * @brief N(i,j) = 
 * @param a, sequence A
 * @param len_a, length of A
 * @param b, sequence B
 * @param len_b, length of B
 */ 
extern int32_t ssm_dp(const char *a, size_t len_a, const char *b, size_t len_b);

/**
 * acs_dp, All-Common-Subquence 
 * all diff sub-sequences of A match a sub-sequences of B
 * @param a, sequence A
 * @param len_a, length of A
 * @param b, sequence B
 * @param len_b, length of B
 */
extern int32_t acs_dp(const char *a, size_t len_a, const char *b, size_t len_b);

/**
 * lcs_dp, Longest-Common-Subquence 
 * A & B longest common subquence
 * @return the length of LCS or < 0(error)
 * @param a, sequence A
 * @param len_a, length of A
 * @param b, sequence B
 * @param len_b, length of B
 * @param res[out], the LCS begin pointer in first substring
 * @param len_r[out], the length of LCS
 */
extern int32_t lcs_dp(const char *a, size_t len_a, const char *b, size_t len_b,
		      char *res, size_t *len_r);

/**
 * lis_dp, Longest-increasing-Subquence 
 * A longest increasing subquence
 * O(n^2) not O(nlgn)
 * @param a, sequence A
 * @param len_a, length of A
 * @param res[out], the LIS begin pointer in first substring
 * @param len_r[out], the length of LIS
 */
extern int32_t lis_dp(const char *a, size_t len_a, char *res, size_t *len_r);

/**
 * edit-distance, levenshtein-distance 
 * the distance between two words 
 * @param a, sequence A
 * @param len_a, length of A
 * @param b, sequence B
 * @param len_b, length of B
 * @param res[out], the desc array for a => b
 */
extern int32_t levenshtein(const char *a, size_t len_a, const char *b,
			   size_t len_b, char *res);

/**
 * str_similar_lcs
 * calculate similarity of two strings use LCS
 * @return  -1.0, error, 0<=ret<=1, similarity, bigger is better
 * @param str_a
 * @param len_a
 * @param str_b
 * @param len_b
 */
extern float str_similar_lcs(const char *str_a, size_t len_a,
			     const char *str_b, size_t len_b);

/**
 * str_similar_ld
 * calculate similarity of two strings use LD
 * @return  -1.0, error, 0<=ret<=1, similarity, bigger is better
 * @param str_a
 * @param len_a
 * @param str_b
 * @param len_b
 */
extern float str_similar_ld(const char *str_a, size_t len_a,
			    const char *str_b, size_t len_b);

#ifdef __cplusplus
}
#endif
#endif
